\documentclass[12pt]{report}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{indentfirst}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{geometry}
\usepackage{listings}
\usepackage{amsmath}
\frenchspacing


\geometry{verbose,tmargin=2.5cm,bmargin=3.5cm,lmargin=2cm,rmargin=2cm}

\renewcommand{\thesection}{\arabic{section}}



\author{Mohamed El Fardi\\ Lo\"ic Fournier\\ Yann Hauquin}
\title{Projet AMR\\Coloration de graphes}
\date{\today}
\begin{document}

\maketitle


\renewcommand{\labelitemi}{\textbullet}

\section*{Avant de commencer}

\begin{itemize}

\item{Notre structure de données \textit{Graphe} utilise une liste
  d'adjacence. Elle permet d'accéder à un sommet en
  \textit{O(n)}, contrairement à une implémentation avec une matrice, où l'accès se fait en
  \textit{O($n^{2}$)}. Vis à vis de l'utilisation mémoire, la matrice
  utilise une portion mémoire de taille $n^{2}$ dans \textbf{tous les cas}. La
  liste d'adjacence quant à elle, utilise dans le pire des cas une portion mémoire de
  taille $n^{2}$ et de taille $n$ dans le cas d'un graphe sans
  arête.\\}

\item{Notre code est écrit en \textit{C++}. Il permet la programmation
  orientée objet. Nous manipulons donc des objets \textit{Node} (=
  une valeur et une couleur) et des objets \textit{Graphe} (= liste de
  listes de \textit{Node}).\\}

\item{Pour une implémentation plus sûre, nous avons utilisé \textit{CPPUnit}
  pour les tests unitaires sur chacun de nos algorithmes.\\}

\end{itemize}

\newpage


% Table des matieres
\tableofcontents

\newpage

\section{Génération de Graphes aléatoires}

\subsection{Graphe aléatoire usuel}

Cet algorithme de création de graphe reste assez trivial. Comme expliqué
dans le sujet, on crée une arête entre chaque sommet selon sa
probabilité. Pour cela, on crée initialement \textit{n} listes (le
\textit{n} étant donné en paramètre au constructeur, correspondant au
nombre de sommets). Chaque liste correspondant à une liste d'adjacence
du graphe. La création d'une arête correspondant à l'insertion d'un
sommet dans la liste d'adjacence courante (en fonction de la
probabilité \textit{p}).

\subsection{Graphe aléatoire \textit{k}-coloriable}

Cet algorithme suit la même règle de création que le précédant, en
ajoutant en plus une règle de coloration. Pour chaque création de
\textit{Node}, on lui attribut une couleur aléatoirement (avec la
probabilité $1/k$).

\section{Algorithmes de coloration}

\subsection{Approximation gloutonne}

\subsubsection{Analyse}

\begin{itemize}
\item{\textit{\textbf{Quelle est le nombre maximum de couleurs que l'algorithme
      pourrait utiliser ?}}}\\
\end{itemize}


Dans le cas d'un graphe complet (probabilité égale à 1), le nombre de
couleurs sera égale au nombre de sommets. Sachant que notre constructeur
interdit la création d'arêtes multiples, le \textit{k-couleur} sera donc
égal (dans le pire des cas = graphe complet) au nombre de sommets.\\

\begin{itemize}
\item{\textit{\textbf{Combien de couleurs (en moyenne) utilise cet
      algorithme pour colorier les graphes k-coloriable?}}}\\
\end{itemize}

Pour le calcul du nombre moyen de couleurs utilisé par cet algorithme,
nous avons utilisé les résultats obtenus sur les tests. Il en ressort
que le nombre de couleurs moyen est égal à $\frac{n} 2 * p$.

\subsubsection{Complexité}

Cet algorithme comporte deux boucles \emph{for} imbriquées. L'une
correspondant au parcours de la liste d'adjacence, l'autre parcourant la
liste des couleurs disponibles. On a donc une complexité égale à
$O(n^{k})$, avec $n$ le nombre de sommets du graphe et $k$ le nombre de
couleurs.

\newpage

\begin{verbatim}
Pour chaque sommet S du graphe G :
   Pour chaque couleur C de la liste des couleurs :
      Si aucun voisin de S n'est de couleur C
         Couleur(S) = C
         Break de la boucle
      Fin Si
      Si G n'est pas entièrement coloré
         Couleur(S) = Nouvelle couleur
      Fin Si
   Fin Pour
Fin Pour
\end{verbatim}

Pour chaque sommet, on teste si une couleur déjà utilisée est
possible pour le sommet courant, si ce n'est pas le cas, on augmente le
nombre de couleurs, on lui attribut la nouvelle couleur, et on passe au
sommet suivant. Au final on se retrouve avec un graphe entièrement coloré.

\subsection{Algorithme \textit{Backtracking}}

\subsubsection{Explication algorithmique}

L'algorithme de backtracking correspond à un empilement de l'arbre
d'exécution.
Dans notre cas, l'arbre d'exécution complet correspond à toutes les possibilités
de coloration du graphe, il est de taille $n^{k}$. Notre algorithme effectue un parcours en
profondeur. A chaque itération, on colorie un sommet selon les couleurs
possibles. Si aucune couleur n'est disponible pour ce sommet, on
dépile. C'est à dire qu'on revient au sommet précédant (on remonte au
père dans l'arbre), et on le colorie
dans la couleur possible suivante. 

\subsubsection{Complexité}

Cet algorithme est un algorithme récursif. Il prend en paramètre un
numéro de sommet (le sommet courant). On calcul la liste des couleurs
admissibles pour ce sommet là (en fonction de ses voisins). On colorie
le sommet pour chacune de ses couleurs, et on rappelle $backtrack()$ sur
chacun de ses voisins. Lorsque l'on a parcouru tous les sommets, on vérifie si le
graphe est entièrement coloré, si tel est le cas, on stoppe la
récursion (récursion terminale). Dans le cas où aucune couleur n'est admissible
pour le sommet courant, on décolore son père (le voisin qui l'a
appelé), et on ne fait rien (on dépile la fonction).

Ce comportement a pour effet de créer un arbre décrivant toutes les
colorations possibles pour le graphe avec k-couleurs.

Dans le pire des cas (cas où le graphe n'est pas k-coloriable),
l'algorithme parcours l'arbre entier, c'est à dire $n^{k}$ possibilités.
Dans le meilleur des cas, cas où l'algorithme trouve une coloration sans
dépiler une seule fois, la complexité est de $O(n)$ (parcours une seule
fois chaque sommet).

\subsection{Algorithme \textit{no choice}}

\subsubsection{Explication algorithmique}

Cet algorithme calcule d'abord la plus grande k-clique du graphe, selon
l'heuristique vue en cours, à savoir :\\
\\
\verb+V = ensemble des sommets+\\
\verb+C = +$\emptyset$ \verb+(clique vide)+\\
\verb+Calculer le degré de tous les sommets+\\
\verb+Tant que V +$\ne \emptyset$\verb+, faire+\\
\verb+    Choisir x +$\in$\verb+ V de plus grand degré+\\
\verb+    C = C +$\cup$ {x}\\
\verb+    V = V +$\cap$ \verb+Voisins(x)+\\
\verb+Fin Tant que+\\

Une fois la k-clique obtenue, on la colorie des k couleurs disponibles. On 
colorie ensuite les autres sommets du graphe qui ont une et une seule couleur
admissible, c'est à dire les sommets que l'on peut colorier que d'une seule 
couleur (d'où le \textit{``no choice''}).

A la fin, si le graphe est entièrement colorié, on a réussit à trouver une 
k coloration du graphe, sinon, on a échoué.

\subsubsection{Implémentation}
Pour trouver la plus grande k-clique du graphe (selon une heuristique), on a utilisé l'algorithme décrit
ci-dessus.

Pour la coloration des autres sommets du graphe possédant une seule couleur
admissible, on utilise une liste composée de tous les sommets non-coloriés. 
A chaque fois qu'un sommet est colorié, on le supprime de la liste. Si la liste 
est vide, il n'y a plus de sommets à colorier, et le graphe est donc k-coloriable.

\subsubsection{Complexité}
On va décrire la complexité de toutes les opérations coûteuses de l'algorithme, dans
le sens où on s'intéresse seulement aux opérations dont la complexité est supérieure
à \textit{O(nombre de sommets)}.
Soient \textit{n} le nombre de sommets du graphe et \textit{m} le nombre d'arêtes.

Pour le calcul du degré de tous les sommets, on doit parcourir tous les sommets
et compter le nombre de voisins, c'est donc une opération en $O(n + m)$. On suppose
ici que la méthode \textit{size} d'une liste en C++ n'est pas une primitive, donc le
calcul du nombre d'éléments d'une liste se fait en \textit{O(nombre d'éléments)}.

Pour choisir le sommet de plus grand degré parmi notre liste \textit{vertices} 
(fonction \textit{getGreaterDegreeNode}), on parcourt la liste à la
recherche du dit sommet (opération en $O(n)$). Cela ne complique pas la complexité
car notre liste \textit{vertices} voit son nombre d'éléments diminuer à chaque
tour de boucle, dû au fait qu'on fait l'intersection des sommets de la liste aux 
sommets voisins du sommet de plus grand degré. On n'a donc pas une complexité en 
$O(n^{2})$ (à part dans le pire des cas qui correspond à un graphe complet), 
mais une complexité moyenne de $O(n + \frac{m}{n} \times \frac{m}{n})$ = $O(n + \frac{m^{2}}{n^{2}})$.
Le premier membre \textit{n} correspond au premier parcours de tous les sommets à
la recherche du plus grand degré, \textit{$\frac{m}{n}$} au nombre moyen de voisins
d'un sommet (cela dépend bien entendu de la probabilité de départ utilisée pour créer
le graphe), et l'autre \textit{$\frac{m}{n}$} au nombre de voisins des voisins du premier
sommet de plus grand degré.

On arrive donc à une complexité totale de $O(n + m + \frac{m^{2}}{n^{2}})$ = $O(\frac{m^{2}}{n^{2}})$
(car $\forall(n,m) \in (V,E), m \leq n^{2}$).

\section{Expérimentation et analyse des algorithmes}

\subsection{Algorithme Glouton}

\subsubsection{Tests \& résultats}

\includegraphics[scale=0.50]{glouton.png}

Les résultats des tests de l'algorithme glouton nous ont permis de trouver facilement la relation qu'il existe entre le nombre moyen de couleurs utilisées, la probabilité p, et le nombre de sommets N. Grâce aux courbes, on en déduit aisément : $NbMoyen_{Couleurs} = \frac{N}2 * p$.

La division par deux s'explique par le fait qu'une arête est relié à deux sommets. La probabilité étant la même pour deux voisins, on divise par deux pour ne pas prendre en compte deux fois la probabilité d'existence pour une même arête.

\subsection{Algorithme Backtracking}

\subsubsection{Tests \& résultats}

\includegraphics[scale=0.50]{backtrack.png}

Ici les résultats obtenus sont cohérents avec ceux attendus. La couverture (en \%) est directement proportionnelle au nombre de couleurs (plus le nombre de couleurs augmente, plus la couverture est importante). A contrario, la couverture est  inversement proportionnelle au nombre de sommets dans le graphe.

Ainsi, on obtient des courbes décroissantes par rapport au nombre de sommets, avec une différence notable en fonction du nombre de couleurs utilisées.

\subsubsection{Améliorations apportées}

\begin{itemize}
\item{Récursion terminale : L'ajout d'une condition supplémentaire dans le déroulement de
  l'algorithme nous permet de terminer l'algorithme dans le cas où une
  coloration possible est trouvée, et éviter ainsi de finir l'arbre
  complet d'exécution.}
\item{Dans le cas d'un graphe non k-coloriable, à l'origine,
  l'algorithme nous renvoyait le nombre de sommets coloriable dans le
  dernier cas dans l'arbre d'exécution. Typiquement, il s'agit du
  chemin le plus à droite dans l'arbre. Une amélioration a consisté à
  garder le nombre maximal de sommets coloriable tout au long du
  déroulement de l'algorithme. Au final, le nombre renvoyé est bien
  le nombre maximal de sommets coloriable pour le graphe et les
  k-couleurs donnés.}
\end{itemize}

\subsection{Algorithme No choice}

\subsubsection{Tests \& résultats}

\includegraphics[scale=0.50]{nochoice.png}

\includegraphics[scale=0.50]{nochoice2.png}

Pour l'algorithme \textit{no-choice}, la différence entre la version optimisée et non-optimisée (voir plus bas pour les explications des différences algorithmiques) est intéressante à analyser.

La version non-optimisée est relativement efficace pour une k-coloration faible (avec un k < 4). Comment une 7-coloration peut-elle être moins efficace qu'une 3-coloration sur le même graphe ? Il s'agit en fait de l'implémentation choisie : No-choice cherche d'abord l'existence d'une k-clique. Si une telle k-clique n'existe pas dans le graphe donné, l'algorithme termine simplement en coloriant les sommets \textit{no-choice} restants. La probabilité de trouver une 3-clique est bien supérieure à la probabilité de trouver une 7-clique, et cela est d'autant plus vrai dans les graphes de petite taille. Cela explique pourquoi \textit{no-choice non-optimisé} n'est pas très efficace pour un nombre de couleurs élevé.

L'optimisation apportée permet de colorier (selon un algorithme très similaire à glouton) le reste des sommets encore coloriable. Ainsi, même si une k-clique est inexistante, la coloration peut continuer avec l'algorithme pseudo-glouton. On se retrouve donc avec une coloration ``logique'', à savoir une couverture proportionnelle au nombre de couleurs donné.

\subsubsection{Améliorations apportées}

Nous avons implémenté deux versions de \textit{no choice}. La première
étant ``naïve''. Elle s'occupe simplement de colorier la plus grande
clique, et de colorier ensuite les sommets ``no choice'' (ayant une
seule couleur admissible).

La deuxième version optimisée reprend la même implémentation que la
version naïve, puis applique ensuite un algorithme ``glouton'' (sans
ajouter de couleurs cependant). La gestion des sommets pas encore
coloriés se faisant par liste, la complexité ne change pas (et reste en $O(n)$).

\subsection{Comparaison}

On remarque que \textit{backtrack} est plus efficace que \textit{no-choice} sur de petits graphes (taille < 40), et inversement pour des graphes de plus grandes tailles (taille > 60).

Sur de petits graphes, la probabilité de trouver une k-clique (pour \textit{no-choice}) reste faible, tandis que le nombre de possibilités (pour \textit{backtrack}) diminue. C'est ce qui explique la différence d'efficacité sur de petits graphes.

Sur de grands graphes, lorsque l'algorithme \textit{backtrack} se retrouve sur une impasse, il termine en laissant une partie du graphe non visitée. En effet, \textit{backtrack} effectue un parcours en largeur, et si une k-coloration n'est plus possible dès le premier quart de l'arbre, \textit{backtrack} laisse les trois autres non coloriés. \textit{No choice} lui colorie (à la manière gloutonne) la liste des sommets encore non coloriés, et ne s'arrête donc pas sur une impasse. C'est ce qui explique la grande différence d'efficacité, notamment sur les k-colorations faibles (k < 4).
\\
\begin{itemize}
\item{Exemple concret :}
\end{itemize}

Sur un graphe de taille 100, si la liste d'adjacence commence par :
\\
\verb+0: 1+\\
\verb+1: 2 3+\\
\verb+2: 1 3+\\
\verb+3: 1 2+\\
\verb+...+\\

\textit{Backtrack} coloriera seulement 3 sommets sur les 100, alors que \textit{no-choice} pourra continuer la coloration sur le reste du graphe (avec le pseudo-glouton).

\section{Solveur SAT}

\subsection{Réduction du problème k-coloration au problème SAT}

\subsubsection{Réduction au problème 3-SAT}

\underline{Instance} : Soit un graphe G = (V,E)

On exprime sous forme de formule logique la propriété d'un graphe d'être
3-coloriable.

\`A tous les sommets i $\in$ V, on associe trois variables : \\

$r_{i}\left\{\begin{tabular}{l}
- 1 si le sommet i est rouge \\
- 0 sinon
\end{tabular}\right .$
\\
\\

$v_{i}\left\{\begin{tabular}{l}
- 1 si le sommet i est vert \\
- 0 sinon
\end{tabular}\right .$
\\
\\

$b_{i}\left\{\begin{tabular}{l}
- 1 si le sommet i est bleu \\
- 0 sinon
\end{tabular}\right .$ 
\\
\\

Chaque sommet a au moins une couleur :\\
$\Phi_{1} = \bigwedge_{i \in V}{(r_{i} \lor v_{i} \lor b_{i})}$
\\

Chaque sommet comporte au plus une couleur:\\
$\Phi_{2} = \bigwedge_{i \in V}{\left[(\lnot r_{i} \lor \lnot
    v_{i})\land(\lnot r_{i} \lor \lnot b_{i})\land(\lnot v_{i} \lor \lnot b_{i})\right]}$
\\

Deux voisins ne comporte pas la même couleur :\\
$\Phi_{3} = \bigwedge_{(i,j) \in E}{\left[\lnot (r_{i} \land r_{j})
    \land \lnot (v_{i} \land v_{j}) \land
    \lnot (b_{i} \land b_{j})\right]}$
\\

Propriété d'un graphe 3-coloriable :\\
$\Phi = \Phi_{1} \land \Phi_{2} \land \Phi_{3}$
\\

\subsubsection{Réduction au problème SAT}

\underline{Instance} : Soit un graphe G = (V,E)

On exprime sous forme de formule logique la propriété d'un graphe d'être
k-coloriable.

\`A tous les sommets i $\in$ V, on associe k variables : \\

$c_{i}^{k}\left\{\begin{tabular}{l}
- 1 si le sommet i est de couleur $c^{k}$ \\
- 0 sinon
\end{tabular}\right .$
\\
\\

Chaque sommet a au moins une couleur :\\
$\Phi_{1} = \bigwedge_{i \in V}{(c_{i}^{1} \lor c_{i}^{2} \lor \dots
  \lor c_{i}^{k})}$
\\

Chaque sommet comporte au plus une couleur:\\
$\Phi_{2} = \bigwedge_{i \in V}{\left[(\lnot c_{i}^{1} \lor \lnot
    c_{i}^2 \lor \dots \lor \lnot c_{i}^{k-1})\land(\lnot c_{i}^{1} \lor
    \lnot c_{i}^{2} \lor \dots \lor \lnot c_{i}^{k-2} \lor \lnot
    c_{i}^{k})\land \dots \land(\lnot c_{i}^{2} \lor \lnot c_{i}^{3} \lor
    \dots \lor \lnot c_{i}^{k})\right]}$
\\

Deux voisins ne comportent pas la même couleur :\\
$\Phi_{3} = \bigwedge_{(i,j) \in E}{\left[\lnot (c_{i}^{1} \land c_{j}^{1})
    \land \lnot (c_{i}^{2} \land c_{j}^{2}) \land \dots \land
    \lnot (c_{i}^{k} \land c_{j}^{k})\right]}$
\\

Propriété d'un graphe k-coloriable :\\
$\Phi = \Phi_{1} \land \Phi_{2} \land \Phi_{3}$
\\

\subsubsection{En pratique...}

A partir des clauses ci-dessus, d'un graphe vierge et d'un nombre de couleurs, on génère 
un fichier CNF qui va être analysé par $minisat$ pour savoir si le problème est 
satisfaisable (c'est à dire résolvable) ou pas. Chaque nombre du fichier CNF correspond à une 
variable, le signe négatif correspond à la négation de la variable (par exemple, -12 correspond
à $\lnot c_{i}^{12}$). Si le problème est satisfaisable, $minisat$ nous renvoie en sortie
un fichier comprenant les valeurs booléennes des variables définies. On en déduit, pour
chaque sommet $i$, une unique couleur qui correspond à sa variable de valeur positive $c_{i}^{l}$
($l \in \{1, \dots, k\}$).

\newpage 
\section{Problèmes rencontrés}

\begin{itemize}
\item Au lieu de stocker directement des objets dans la liste d'adjacence, nous stockons uniquement des adresses (pointeurs). Lors d'une création d'arête (par exemple) il ne faut pas créer un autre objet \textit{Node} mais bien ajouter la même adresse (l'objet en lui même n'est créé qu'une seule fois). Nous avons oublié d'en tenir compte au début du projet dans nos algorithmes. Le résultat de coloration n'était donc pas correcte. Il nous a fallu un certain temps avant de nous rendre compte de notre erreur.
\item Bien que ce ne soit pas tout à fait un problème, nous avions obligation de coder portable, puisque nous codons au sein du groupe à la fois sur Linux et sur Mac OS.
\item Au début du projet, nous pensions passer à peu près autant de temps pour chaque algorithme. Il se trouve que la partie \textit{no-choice}  nous a pris plus de temps que prévu. En conséquence, il a fallu doubler le temps de travail dans les derniers jours pour pouvoir clore la partie \textit{minisat}.
\end{itemize}

\end{document}
